package 链表;

/**
 * <p>
 * https://leetcode-cn.com/problems/reverse-linked-list/
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * 进阶:
 * 你可以迭代或递归地反转链表。
 * </p>
 *
 * @author AJun
 * @since 2020/8/12
 */
public class _206_反转链表 {

    /**
     * 递归
     */
    public ListNode reverseList(ListNode head) { // 5 4 3 2 1 head = 5
        if (head == null || head.next == null)
            return head;

        ListNode newHead = reverseList(head.next); // 4 3 2 1  => 1 2 3 4
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    /**
     * 迭代
     */
    public ListNode reverseList1(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTmp;
        }
        return prev;
    }

}
